[JSOI2015] 骗我呢

发布于 2021-02-03 | 分类于容斥原理 | 8分钟 | 1606字数

Description

题面挺长的所以挂个链接

Solution

首先观察一下题面：它的值域不大。

阅读全文 »

UOJ499 喂鸽子

发布于 2021-02-01 | 分类于反演相关 | 8分钟 | 1425字数

Description

题面挺长挂个链接

Solution

「所有的鸽子都饱了」本质就是求每个鸽子第一次饱的时刻的最大值嘛，由于第一次本应是「最小」的含义，所以最值反演一手。

阅读全文 »

Luogu5221 Product

发布于 2021-01-31 | 分类于数论函数相关、反演相关 | 4分钟 | 754字数

Description

给定 $n$ ，求下式的值

\prod_{i=1}^{n}\prod_{j=1}^{n}\frac{\text{lcm}(i,j)}{\text{gcd}(i,j)}

阅读全文 »

联合省选2020 作业题

发布于 2021-01-29 | 分类于矩阵树定理、数论函数相关 | 7分钟 | 1277字数

Description

题面挺长的所以挂链接

Solution

听说这是两个经典 trick 的结合，mark 一下。

阅读全文 »

CF1139D Steps to One

发布于 2021-01-28 | 分类于反演相关 | 4分钟 | 609字数

Description

给一个数列，每次随机从 $[1,m]$ 中选择一个数添加到数列末尾，直至数列的 $\gcd =1$ 时停止。求期望长度。
$1\leq m\leq 10^5$

Solution

阅读全文 »

Quiz 0127 summary

发布于 2021-01-28 | 分类于比赛报告 | 9分钟 | 1683字数

T1 COCI2019 Quiz

Description

题面不长但是放个链接算惹

Solution

阅读全文 »

ARC101E Ribbons on Tree

发布于 2021-01-27 | 分类于容斥原理、树形 dp | 5分钟 | 1021字数

Description

给定一棵大小为 $n$ 的树，你需要给树上的点两两配对，对于一组对子 $(u,v)$ ，在树上将 $u\rightarrow v$ 的路径染色。定义一个配对方案合法当且仅当所有边都有颜色。
求方案数对 $10^9 + 7$ 取模。
$n\leq 5\times 10^3,2|n$

阅读全文 »

树形 DP 泛做

发布于 2021-01-25 | 分类于树形 dp 、学习笔记 | 14分钟 | 3393字数

博主鉴于自己的树形 dp 水平太 low 前段时间专门练习了下树形 dp。
就把题解和方法整理在一篇博客里算了。
希望自己以后遇到树形 dp 的题目能有更多准确的想法吧 🌹。

阅读全文 »

六省联考2017 解题报告

发布于 2021-01-24 | 分类于比赛报告 | 23分钟 | 4442字数

T1 寿司餐厅

Description

太长了挂个链接算惹

Solution

阅读全文 »

[ZJOI2017] 仙人掌

发布于 2021-01-23 | 分类于树形 dp 、计数 dp | 5分钟 | 903字数

Description

如果一个无自环无重边无向连通图的任意一条边最多属于一个简单环，我们就称之为仙人掌。所谓简单环即不经过重复的结点的环。现在给定一张无自环无重边的无向连通图，求有多少种合法的加边方案，使得加边后原图是张仙人掌图。 $T$ 组测试数据。

$\sum n\leq 5\times 10^5,\sum m\leq 10^6$

Solution

阅读全文 »